package com.tys.algorithm.advanced.test.class18;

/**
 * 拿纸牌最右最左的获胜分数
 * 给定一个整型数组arr，代表数值不同的纸牌排成一条线
 * 都能看到牌
 * 玩家A和玩家B依次拿走每张纸牌
 * 规定玩家A先拿，玩家B后拿
 * 但是每个玩家每次只能拿走最左或最右的纸牌
 * 玩家A和玩家B都绝顶聪明
 * 请返回最后获胜的分数
 * 1 100 1
 * 100 1
 */
public class Code02_CardsInLine {

    // 方法1：
    // 根据规则，返回获胜者的分数
    public static int win1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        //先手获得最大
        int first = f1(arr, 0, arr.length - 1);
        //后手获得最大
        int second = g1(arr, 0, arr.length - 1);
        //选最大
        return Math.max(first, second);
    }

    //先手
    // arr[L..R]，先手获得的最好分数返回
    public static int f1(int[] arr, int L, int R) {
        //只剩一张牌
        if (L == R) {
            //先手拿走
            return arr[L];
        }
        //拿走左侧牌
        int p1 = arr[L] + g1(arr, L + 1, R);
        //拿走右侧排
        int p2 = arr[R] + g1(arr, L, R - 1);
        //选拿左和拿右最大的
        return Math.max(p1, p2);
    }

    // 后手
    // arr[L..R]，后手获得的最好分数返回
    public static int g1(int[] arr, int L, int R) {
        //剩一张牌
        if (L == R) {
            //被先手拿走，后手没有牌
            return 0;
        }
        //从f拿走后剩余的选最优
        int p1 = f1(arr, L + 1, R); // 对手拿走了L位置的数
        int p2 = f1(arr, L, R - 1); // 对手拿走了R位置的数
        //后手获得最小值：因为先手会给后手留最小值
        return Math.min(p1, p2);
    }

    //方法2：傻缓存
    public static int win2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int N = arr.length;
        //加缓存
        //f的缓存
        int[][] fmap = new int[N][N];
        //g的缓存
        int[][] gmap = new int[N][N];
        //初始化化缓存设置为-1
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                fmap[i][j] = -1;
                gmap[i][j] = -1;
            }
        }
        int first = f2(arr, 0, arr.length - 1, fmap, gmap);
        int second = g2(arr, 0, arr.length - 1, fmap, gmap);
        return Math.max(first, second);
    }

    // arr[L..R]，先手获得的最好分数返回
    public static int f2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) {
        //不等于-1就是算过了，直接返回
        if (fmap[L][R] != -1) {
            return fmap[L][R];
        }
        //记录答案
        int ans = 0;
        if (L == R) {
            ans = arr[L];
        } else {
            int p1 = arr[L] + g2(arr, L + 1, R, fmap, gmap);
            int p2 = arr[R] + g2(arr, L, R - 1, fmap, gmap);
            ans = Math.max(p1, p2);
        }
        //记录缓存
        fmap[L][R] = ans;
        return ans;
    }

    // // arr[L..R]，后手获得的最好分数返回
    public static int g2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) {
        //不等于-1，计算过直接返回
        if (gmap[L][R] != -1) {
            return gmap[L][R];
        }
        //答案：默认0
        int ans = 0;
        if (L != R) {
            //从f拿走后剩余的选最优
            int p1 = f2(arr, L + 1, R, fmap, gmap); // 对手拿走了L位置的数
            int p2 = f2(arr, L, R - 1, fmap, gmap); // 对手拿走了R位置的数
            ans = Math.min(p1, p2);
        }
        //记录缓存
        gmap[L][R] = ans;
        return ans;
    }

    //方法3：
    public static int win3(int[] arr) {
        //数组空返回0
        if (arr == null || arr.length == 0) {
            return 0;
        }
        //缓存
        int N = arr.length;
        int[][] fmap = new int[N][N];
        int[][] gmap = new int[N][N];
        //初始化 f 缓存对角线为数组值
        for (int i = 0; i < N; i++) {
            fmap[i][i] = arr[i];
        }
        //开始列从1开始，不能超过N
        for (int startCol = 1; startCol < N; startCol++) {

            int L = 0;
            int R = startCol;
            while (R < N) {
                //取最大：在表中拿值，左和右旋最大
                fmap[L][R] = Math.max(arr[L] + gmap[L + 1][R], arr[R] + gmap[L][R - 1]);
                //取最小：在表中拿值，左和右选最小
                gmap[L][R] = Math.min(fmap[L + 1][R], fmap[L][R - 1]);
                //顺着对角线走
                L++;
                R++;
            }
        }
        return Math.max(fmap[0][N - 1], gmap[0][N - 1]);
    }

    public static void main(String[] args) {
        int[] arr = {5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7};
        System.out.println(win1(arr));
        System.out.println(win2(arr));
        System.out.println(win3(arr));

    }

}
